package com.unionfind_01;

/**
 * @Author: tgy
 * @Date: 1/11/21 3:03 PM
 *
 * UF => union find
 *
 *           p1                 p2
 *        /  \ \  \           /  \   \
 *     v1   v2  v3   v4      v5  v6  v7
 *
 *  quick find
 *  find 时间复杂度为 O(1)
 *  union 时间复杂的度为 O(n)
 */
public class UF_QuickFind extends AbstractUnionFind{

    public UF_QuickFind(int size) {
        super(size);
    }

    @Override
    public int find(int v) {

        return parents[v];
    }

    @Override
    public void union(int v1, int v2) {

        int p1 = find(v1);
        int p2 = find(v2);

        if (p1 == p2) {

            return;
        }

        for (int i = 0; i < parents.length; i++) {

            if (parents[i] == p2) {

                parents[i] = p1;
            }
        }

    }

    public static void main(String[] args) {

        UF_QuickFind quickFind = new UF_QuickFind(9);

        quickFind.union(1,4);
        quickFind.union(2,5);
        quickFind.union(3,7);
        quickFind.union(3,4);

        System.out.println(quickFind.find(4));

        System.out.println(quickFind.isSame(1, 7));
    }




























}
